Dijkstra's অ্যালগরিদমের টাইম এবং স্পেস কমপ্লেক্সিটি
Dijkstra's অ্যালগরিদমের কমপ্লেক্সিটি নির্ভর করে গ্রাফের প্রকার এবং ডেটা স্ট্রাকচারের ওপর।
টাইম কমপ্লেক্সিটি:
- ব্রুট ফোর্স পদ্ধতি: প্রতিটি নোডের জন্য সর্বনিম্ন ওয়েট খুঁজতে \( O(V^2) \) সময় লাগে, যেখানে \( V \) হলো নোডের সংখ্যা।
মিন হিপ (Min-Heap) বা প্রায়োরিটি কিউ ব্যবহার করলে: এখানে কমপ্লেক্সিটি \( O((V + E) \log V) \), যেখানে \( E \) হলো প্রান্তের সংখ্যা।
এই প্রক্রিয়ায় প্রতিটি প্রান্তের জন্য হিপ অপারেশন \( \log V \) সময় নেয়।
স্পেস কমপ্লেক্সিটি:
Dijkstra's অ্যালগরিদমের জন্য স্পেস কমপ্লেক্সিটি হলো \( O(V) \), যা মূলত প্রতিটি নোডের জন্য দূরত্ব এবং ভিজিটেড অবস্থা সংরক্ষণ করতে ব্যবহৃত হয়।
Floyd-Warshall অ্যালগরিদমের টাইম এবং স্পেস কমপ্লেক্সিটি
Floyd-Warshall অ্যালগরিদম একটি অল-পেয়ারস শর্টেস্ট পাথ সমস্যা সমাধান করে এবং এটি ডায়নামিক প্রোগ্রামিং পদ্ধতির উপর ভিত্তি করে।
টাইম কমপ্লেক্সিটি:
Floyd-Warshall অ্যালগরিদমের টাইম কমপ্লেক্সিটি হলো \( O(V^3) \), যেখানে \( V \) হলো নোডের সংখ্যা। এই অ্যালগরিদমে প্রতিটি নোডকে মধ্যবর্তী নোড হিসেবে বিবেচনা করা হয় এবং প্রতিটি জোড়া নোডের জন্য তাদের দূরত্ব আপডেট করা হয়, তাই \( V^3 \) সময় লাগে।
স্পেস কমপ্লেক্সিটি:
Floyd-Warshall অ্যালগরিদমের স্পেস কমপ্লেক্সিটি হলো \( O(V^2) \), কারণ এটি প্রতিটি নোডের জন্য একটি ডিস্টেন্স ম্যাট্রিক্স সংরক্ষণ করে যা গ্রাফের প্রতিটি নোড থেকে অন্য প্রতিটি নোড পর্যন্ত পথের দূরত্ব ধারণ করে।
সারসংক্ষেপ
- Dijkstra's অ্যালগরিদম: টাইম কমপ্লেক্সিটি \( O((V + E) \log V) \) (মিন হিপের জন্য) এবং স্পেস কমপ্লেক্সিটি \( O(V) \)।
- Floyd-Warshall অ্যালগরিদম: টাইম কমপ্লেক্সিটি \( O(V^3) \) এবং স্পেস কমপ্লেক্সিটি \( O(V^2) \)।
Dijkstra's অ্যালগরিদম একক উৎস থেকে সংক্ষিপ্ততম পথ নির্ণয়ে কার্যকর, আর Floyd-Warshall অ্যালগরিদম পুরো গ্রাফের প্রতিটি নোডের মধ্যে সংক্ষিপ্ততম পথ নির্ণয় করতে কার্যকর।
